package _022_04_05

import (
	"fmt"
	"math"
	"math/bits"
	"strings"
)

/*
给你两个整数left和right ，在闭区间 [left, right]范围内，统计并返回 计算置位位数为质数 的整数个数。

计算置位位数 就是二进制表示中 1 的个数。

例如， 21的二进制表示10101有 3 个计算置位。

提示：
1 <= left <= right <= 106
0 <= right - left <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

func countPrimeSetBits1(left int, right int) int {
	count := 0
	for num := left; num <= right; num++ {
		if isPrime(getSetBits(num)) {
			count++
		}
	}

	return count
}

// 计算置位位数
func getSetBits(num int) int {
	s := fmt.Sprintf("%b", num)
	return strings.Count(s, "1")
}

// 判断一个数是不是质数
func isPrime(num int) bool {
	if num <= 1 {
		return false
	}

	if num == 2 || num == 3 {
		return true
	}

	if num%2 == 0 {
		return false
	}

	sqr := int(math.Sqrt(float64(num)))

	for i := 3; i <= sqr; i += 2 {
		if num%i == 0 {
			return false
		}
	}
	return true
}

func countPrimeSetBits2(left, right int) (ans int) {
	for x := left; x <= right; x++ {
		if isPrime(bits.OnesCount(uint(x))) {
			ans++
		}
	}
	return
}

func countPrimeSetBits(left, right int) (ans int) {
	for x := left; x <= right; x++ {
		if 1<<bits.OnesCount(uint(x))&665772 != 0 {
			ans++
		}
	}
	return
}
